A program in execution needs memory to store the data manipulated by the program. Memory is allocated in various ways. In the earliest form of memory allocation, called static allocation, a variable was bound to a chunk of memory at compile time and did not change throughout the program execution. In the case of stack allocation, the binding was created during the invocation of the function that has the variable in its scope and lasts for the lifetime of the function. In heap allocation, the binding was created explicitly by executing a statement that allocates a chunk of memory and explicitly binds an access expression to the chunk of memory.
An object is a collection of data in memory that is stored at consecutive addresses. Unless the object is extremely small, objects are located at more than one address and in some systems can move. A pointer is an instance of a programming language data type whose value refers directly to (or ‘points to’) an object stored elsewhere in the memory using its address. Conventionally, the address of the start of the object is used. This is the address of the piece of data belonging to the object that has the lowest numerical value. The parts of which an object is comprised can be called fields, elements, properties, members or slots.
An access expression is a generalization of a variable and denotes an object. Access expressions can be part of objects. One of the ways in which the binding between an access expression and an object can be undone is by disposing of the activation record that contains the access expression. Then, the access expression ceases to have any meaning.
The other way is to execute an assignment statement that will bind the access expression to a different object or no object at all. After a binding is changed, the chunk of memory containing an object may be unreachable. Since an object may contain access expressions, this may lead to other chunks of memory becoming unreachable. An issue is the reclamation of such unreachable memory. The reclaimed memory can be subsequently allocated to different objects whose addresses are bound to different access expression.
An automatic tool that can detect unreachable memory and reclaim it frees the programmer from concerns of memory management. In the context of heap allocation, an unreachable memory chunk is called garbage, and a tool that detects and collects garbage is called a garbage collector. The executing program whose memory requirements are being serviced by the garbage collector is called the mutator. A garbage collector is an advanced ‘memory manager’. The term memory manager is used herein to designate a more general concept than does garbage collector.
During the course of operation, the mutator occasionally needs to adjust the data that the garbage collection subsystem maintains. This can happen when the mutator writes a value to memory, modifying that memory. Conversely, the garbage collector occasionally needs to adjust the data that the mutator is using. This can happen when the mutator reads a value from memory. These adjustments are controlled by so-called ‘read barriers’ and ‘write barriers’, which determine which mutator operations require special processing and ensure that the special processing takes place. Barriers are single or multiple instructions inserted at the relevant points in the mutator code for this purpose.
Many garbage copying garbage collectors use short pauses, during which the garbage collectors perform garbage collection (often using independently collectable regions to make the collection incremental). In many applications, such as real time data streaming, the shorter the pause time the better.